#ifndef HEAP_H_
#define HEAP_H_

#include <algorithm>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>
#include <xutility>

namespace lxj
{
template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
class Heap {
public:
    enum class HeapStructure
    {
        BIG,
        SMALL
    };

private:
    std::vector<T> m_heap;
    size_t         m_size;
    HeapStructure  m_hs;

    void swap(T& a, T& b)
    {
        T temp = a;
        a      = b;
        b      = temp;
    }

public:
    template<class Iter>
    Heap(Iter first, Iter last, HeapStructure HS = HeapStructure::BIG)
    {
        if (first == last) return;
        std::_Adl_verify_range(first, last);

        auto ufirst = std::_Get_unwrapped(first);
        auto ulast  = std::_Get_unwrapped(last);

        m_hs   = HS;
        m_size = ulast - ufirst;
        m_heap.reserve(m_size);
        m_heap.assign(ufirst, ulast);

        // 由顶向底建堆
        /* for (size_t i = 0; i < m_heap.size(); i++) {
            heap_insert(i);
        } */

        // 由底向顶建堆
        for (int i = m_heap.size() - 1; i >= 0; i--) {
            heapify(i);
        }
    }

    // i位置的数，向上调整堆
    void heap_insert(int32_t i)
    {
        if (i > m_size) return;

        auto insert = [this, i](auto Pred = std::greater<T>()) mutable {
            while (Pred(m_heap[i], m_heap[(i - 1) / 2])) {
                swap(m_heap[i], m_heap[(i - 1) / 2]);
                i = (i - 1) / 2;
            }
        };

        if (m_hs == HeapStructure::BIG) {
            insert(std::greater<T>());
        }
        else {
            insert(std::less<T>());
        }
    }

    // i位置的数，向下调整堆
    void heapify(int32_t i)
    {
        int32_t l = i * 2 + 1;

        auto fy = [this, i, l](auto Pred = std::greater<T>()) mutable {
            while (l < m_size) {
                int32_t best = l + 1 < m_size && Pred(m_heap[l + 1], m_heap[l]) ? l + 1 : l;
                best         = Pred(m_heap[best], m_heap[i]) ? best : i;
                if (i == best) break;
                swap(m_heap[i], m_heap[best]);
                i = best;
                l = i * 2 + 1;
            }
        };

        if (m_hs == HeapStructure::BIG) {
            fy(std::greater<T>());
        }
        else {
            fy(std::less<T>());
        }
    }

    /* T get_value(size_t i) const
    {
        if (i >= m_size) return INT32_MIN;
        return m_heap[i];
    } */

    T top() const { return m_heap.empty() ? INT_MIN : m_heap[0]; }

    void pop()
    {
        for (size_t i = 0, j = 1; j < m_heap.size(); i++, j++) {
            m_heap[i] = m_heap[j];
        }
        m_size--;
        for (int i = m_heap.size() - 1; i >= 0; i--) {
            heapify(i);
        }
        m_heap.resize(m_size);
    }

    void push(T value)
    {
        m_heap.push_back(value);
        heap_insert(m_size);
        m_size += 1;
    }

    void heap_sort()
    {
        size_t size = m_size;
        while (m_size != 0) {
            swap(m_heap[0], m_heap[--m_size]);
            heapify(0);
        }
        m_size = size;
    }
};

// 合并 K 个升序链表
struct ListNode {
    int       val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
inline ListNode* mergeKLists(std::vector<ListNode*>& lists)
{
    auto comp = [](ListNode* l, ListNode* r) { return std::greater<int>()(l->val, r->val); };
    std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(comp)> heap(comp);
    for (auto& i : lists) {
        i != nullptr ? heap.push(i) : void();
    }
    if (heap.empty()) return nullptr;
    ListNode* h = heap.top();
    heap.pop();
    ListNode* pre = h;
    while (!heap.empty()) {
        if (pre->next != nullptr) heap.push(pre->next);
        pre->next = heap.top();
        pre       = pre->next;
        heap.pop();
    }
    return h;
}

// 线段最多重合问题
inline std::pair<int, int> lineseg_coc(std::vector<std::pair<int, int>> lineseg)
{
    std::sort(lineseg.begin(), lineseg.end(), [](auto begin, auto end) {
        return begin.first < end.first;
    });

    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;

    unsigned short max_seg = 0;
    int            l       = 0;
    int            r       = 0;
    int            past_l  = l;
    int            past_r  = r;
    for (auto& p : lineseg) {
        if (!heap.empty() && p.first >= heap.top()) {
            unsigned short right_count = 0;
            past_r                     = heap.top();
            while (p.first >= heap.top()) {
                heap.pop();
                right_count++;
            }
            right_count += heap.size();
            if (max_seg < right_count) {
                max_seg = right_count;
                l       = past_l;
                r       = past_r;
            }
        }
        heap.push(p.second);
        past_l = p.first >= heap.top() ? past_l : p.first;
    }

    if (!heap.empty() && heap.size() > max_seg) {
        l = past_l;
        r = heap.top();
    }

    return std::make_pair(l, r);
}

// 区间合并
inline std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals)
{
    auto swap = [&intervals](size_t l, size_t r) mutable {
        std::vector<int> temp = intervals[l];
        intervals[l]          = intervals[r];
        intervals[r]          = temp;
    };
    for (int32_t i = intervals.size() - 1; i > 0; i--) {
        size_t max = 0;
        for (int32_t j = 0; j <= i; j++) {
            max = intervals[max][0] >= intervals[j][0] ? max : j;
        }
        swap(i, max);
    }

    std::vector<std::vector<int>> ans;
    ans.reserve(intervals.size());
    std::priority_queue<int, std::vector<int>, std::less<int>> heap;
    int                                                        l = intervals[0][0], r = 0;
    for (auto& v : intervals) {
        if (!heap.empty() && v[0] > heap.top()) {
            r = heap.top();
            while (!heap.empty()) {
                heap.pop();
            }
            ans.emplace_back(std::vector<int>{l, r});
            l = v[0];
        }
        heap.push(v[1]);
    }
    r = heap.top();
    while (!heap.empty()) {
        heap.pop();
    }
    ans.emplace_back(std::vector<int>{l, r});
    return ans;
}

// 让数组整体累加和减半的最少次数 力扣2208
inline int halveArray(std::vector<int>& nums)
{
    Heap<double> heap(nums.begin(), nums.end());
    // std::priority_queue<double> heap(nums.begin(), nums.end());

    const double half_sum = [&nums] {
        double sum = 0.0;
        for (auto i : nums) {
            sum += i;
        }
        return sum / 2;
    }();

    unsigned int count = 0;
    for (double s = 0.0; s < half_sum;) {
        const double half_top = heap.top() / 2;
        s += half_top;
        heap.pop();
        heap.push(half_top);
        count++;
    }
    return count;
}

}   // namespace lxj

#endif